package 热题100;

import java.util.Arrays;

public class 热题38下一个排列复习 {

    public static void main(String[] args) {
        热题38下一个排列复习 o = new 热题38下一个排列复习();
        int[] arr = {1,3,2};
        o.nextPermutation(arr);
    }


    /*
    思路：
    1，如果所有得数都是降序排列，直接返回逆序输出结果
    2，从后向前遍历，找到第一个比index位置小的，交换，
    3，如果在2得位置没有找到最小得，那么就讲index得位置向前移动一位
     */


    public void nextPermutation(int[] nums) {
        for (int i = 0; i < nums.length-1; i++) {
            //如果全是降序排列，逆序返回，若干有前一个比后一个小，就不是最大得
            if (nums[i] < nums[i+1]){
                break;
            }
            //如果比较已经到了最后两个位置，并且已经满足了全部降序，那么就排列成升序，然后返回
            if (i == nums.length - 2){
                Arrays.sort(nums);
                return;
            }
        }

        //2，说明不是全部得降序，存在升序得结果,那么就开始从后向前遍历，找第一个比当前位置小得元素
        int index = nums.length - 1;
        boolean flag = false;
        //i为当前得位置，j从最后一开始寻找，找到第一个前面小后面大得元素，交换这两个位置得元素，对后面i+1到arr.length-1得位置进行排序
        for (int i = index; i >= 0 ; i--) {
            //找到 第一个 降序得拐点
            for (int j = i-1; j >= 0; j--) {
                if (nums[i] > nums[j]){
                    swap(nums,i,j);
                    //交换完成以后，需要对i+1到num.length得位置进行升序排列
                    Arrays.sort(nums,j,nums.length);
                    return;
                }
            }
        }
    }
    private void swap(int[] arr,int i,int j){
        int tem = arr[i];
        arr[i] = arr[j];
        arr[j] = tem;
    }

}
